
\section{Minimum weight polygon triangulation}
\label{sec:polygonTriangulation}

\subsection{Relevance for the project}The LMT skeleton may contain holes. These hole polygons can be triangulated optimally in polynomial time ($O(n^3)$) using a dynamic programming approach.
\begin{figure}[h]
\includegraphics[width=60mm]{lmt_hole.png}
\caption{A LMT skeleton that contains a hole polygon}
\end{figure}

\subsection{Finding the holes in the lmt skeleton}
The first step is to find the hole polygons inside the LMT skeleton. Identifying the vertices that are part of a polygon is not enough, because they also must be in the right order. Figure 1 illustrates the problem that it is possible that there are multiple cycles within a polygon: Vertex $1$ and vertex $2$ are both part of the polygon, but the edge between them is not. The algorithm must find the cycle that contains all vertices of the polygon. This is achieved using a slightly modified depth-first search (cycle search).

\subsection{MWT polygon triangulation algorithm}Given a convex polygon $P = \{v_1, ..., v_n\}$ in anti-clockwise order, we define $t[i,j]$ as the weight of the optimal triangulation of the polygon right to the directed chord between $v_i$ and $v_j$. The weight between two neighbored vertices is $0$. Otherwise, $v_i$ and $v_j$ form a triangle together with a third vertex k with $i<k<j$. $t[i,j]$ is the weight of this triangle plus the minimal triangulation cost of the polygon right to the chord between $i$ and $k$ ($t[i,k]$) and the minimal triangulation cost of the polygon right to the chord between $k$ and $j$ ($t[k,j]$):\\\\
$t[i,j] = \begin{cases}
0 & \text{if }j = i+1\\
min_{i<k<j}(t[i,k] + t[k,j] + w(v_i,v_k,v_j)) & \text{if } j > i + 1
\end{cases}$\\\\
The weight of $t[0, n]$ is the weight of the optimal triangulation of the complete polygon.\\\\
The algorithm only works with convex polygons, but often the lmt holes are not convex. In order to work with all simple polygons correctly, the algorithm must check for each chord between $i$ and $j$ if it is completely inside the polygon. If it is not, we define $t[i,j]$ as $\infty$, because the chord is not part of a valid triangulation and must not be chosen.\\\\
$t[i,j] = \begin{cases}
0 & \text{if }j = i+1\\
\infty & \text{if the chord between $i$ and $j$ is not inside the polygon}\\
min_{i<k<j}(t[i,k] + t[k,j] + w(v_i,v_k,v_j)) & \text{if } j > i + 1
\end{cases}$\\\\